package org.example.sep_24;

import java.util.Stack;

public class Topic_32 {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() < 2){
            return 0;
        }
        int[] dp = new int[s.length()];
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    int prev = stack.pop();
                    dp[i] = (prev > 0 ? dp[prev - 1] : 0) + 2;
                    if (prev - 1 >= 0) {
                        dp[i] += dp[prev - 1];
                    }
                    maxLen = Math.max(maxLen, dp[i]);
                } else {
                    dp[i] = 0;
                }
            }
        }

        return maxLen;
    }
    public static void main(String[] args) {
        Topic_32 topic = new Topic_32();
        String s1 = "(()";
        System.out.println(topic.longestValidParentheses(s1));

        String s2 = ")()())";
        System.out.println(topic.longestValidParentheses(s2));

        String s3 = "";
        System.out.println(topic.longestValidParentheses(s3));

        String s4 = "()(()";
        System.out.println(topic.longestValidParentheses(s4));
    }
}
